package com.formula.datastructure.exercise.graph.undirect;

import com.formula.datastructure.standard.queue.Queue;

/**
 * 方法
 * create
 * insert Vertex
 * delete Vertex
 * insert edge
 * delete edge
 * DFSTraverse 深度遍历
 * BFSTraverse 广度遍历
 */
public class ListGraph {
    public ListVertex[] vertexList;
    public ListEdge[] egdgList;
    int[] visited;
    int nextVexIdx;
    int nextEdgeIdx;

    public ListGraph() {
        vertexList = new ListVertex[20];
        egdgList = new ListEdge[20];
        visited = new int[20];
        nextVexIdx = 0;
        nextEdgeIdx = 0;
    }

    public ListGraph(int size) {
        vertexList = new ListVertex[size];
        egdgList = new ListEdge[size * (size - 1)];
        visited = new int[size];
        nextVexIdx = 0;
        nextEdgeIdx = 0;
    }

    public int vertexSize() {
        return nextVexIdx;
    }

    public int edgeSize() {
        return nextEdgeIdx;
    }

    public int insertVex(ListVertex vertex) {
        vertexList[nextVexIdx++] = vertex;
        ListEdge tempEdge = vertex.firstEdge;
        while (tempEdge != null) {
            egdgList[nextEdgeIdx++] = tempEdge;
            tempEdge = tempEdge.nextEdge;
        }
        return nextVexIdx - 1;
    }

    // 深度遍历
    public void DFSTraverse(int idx) {
        visited[idx] = 1;
        visit(vertexList[idx]);
        ListEdge tempEdge = vertexList[idx].firstEdge;
        while (tempEdge != null) {
            if (visited[tempEdge.toIdx] == 0) {
                // 这里不要写错了
                DFSTraverse(tempEdge.toIdx);
            }
            tempEdge = tempEdge.nextEdge;
        }
    }

    // 广度遍历
    public void BFSTraverse(int idx) {
        Queue queue = new Queue();
        queue.enQueue(idx);
        // 图有回路, 要考虑到这一点, 仍然需要visited
        while (!queue.isEmpty()) {
            idx = (int) queue.deQueue();
            visit(vertexList[idx]);
            ListEdge tempEdge = vertexList[idx].firstEdge;
            while (tempEdge != null) {
                if (visited[tempEdge.toIdx] == 0) {
                    queue.enQueue(tempEdge.toIdx);
                    // 非常重要, visited写在里面
                    visited[tempEdge.toIdx] = 1;
                }
                tempEdge = tempEdge.nextEdge;
            }
        }
    }

    public void visit(ListVertex vertex) {
        System.out.println(vertex.data);
    }

    public static void main(String[] args) {
        ListGraph graph = new ListGraph();
        ListVertex A = new ListVertex("A");
        ListVertex B = new ListVertex("B");
        ListVertex C = new ListVertex("C");
        ListVertex D = new ListVertex("D");
        ListVertex E = new ListVertex("E");
        ListVertex F = new ListVertex("F");

        ListEdge edge1 = new ListEdge(1, 5);
        ListEdge edge2 = new ListEdge(3, 9);
        A.addEdge(edge1);
        A.addEdge(edge2);

        ListEdge edge3 = new ListEdge(2, 2);
        ListEdge edge4 = new ListEdge(3, 10);
        B.addEdge(edge3);
        B.addEdge(edge4);

        ListEdge edge5 = new ListEdge(4, 8);
        ListEdge edge6 = new ListEdge(5, 7);
        C.addEdge(edge5);
        C.addEdge(edge6);

        ListEdge edge7 = new ListEdge(4, 4);
        D.addEdge(edge7);


        ListEdge edge8 = new ListEdge(5, 7);
        E.addEdge(edge8);

        ListEdge edge9 = new ListEdge(1, 6);
        F.addEdge(edge9);

        graph.insertVex(A);
        graph.insertVex(B);
        graph.insertVex(C);
        graph.insertVex(D);
        graph.insertVex(E);
        graph.insertVex(F);

        System.out.println(graph.vertexSize());
        System.out.println(graph.edgeSize());

        //graph.DFSTraverse(0);
        System.out.println();
        graph.BFSTraverse(0);
    }
}